Projekt zespołowy (projekt nr 1) Analiza i Wizualizacja Danych

Drzewa decyzyjne (Decision tree)

                                                                                                    Kamil Donda
                                                                                                    Remigiusz Drobinski

Definicja

Drzewa decyzyjne są graficzną metodą wspomagania procesu decyzyjnego. Jest to jedna z najczęściej wykorzystywanych technik analizy danych. Drzewa składają się z korzenia oraz gałęzi prowadzących z korzenia do kolejnych wierzchołków. Wierzchołki, z których wychodzi co najmniej jedna krawędź, są nazywane węzłami, a pozostałe wierzchołki – liśćmi. W każdym węźle sprawdzany jest pewien warunek dotyczący danej obserwacji, i na jego podstawie wybierana jest jedną z gałęzi prowadząca do kolejnego wierzchołka. Klasyfikacja danej obserwacji polega na przejściu od korzenia do liścia i przypisaniu do tej obserwacji klasy zapisanej w danym liściu.

Zastosowanie drzew decyzyjnych

Drzewa decyzyjne znajdują praktyczne zastosowanie w różnego rodzaju problemach decyzyjnych, szczególnie takich gdzie występuje dużo rozgałęziających się wariantów, a także w warunkach ryzyka. Wiele algorytmów uczenia się wykorzystuje drzewa decyzyjne do reprezentacji hipotez. Zgodnie z ogólnym celem uczenia się indukcyjnego, dążą one do uzyskania drzewa decyzyjnego klasyfikującego przykłady trenujące z niewielkim błędem próbki i o możliwie niewielkim rozmiarze, w nadziei, że takie drzewo będzie miało również niewielki błąd rzeczywisty. Drzewa decyzyjne znajdują szerokie zastosowanie w problemach związanych z klasyfikacją i predykcją pojęć typu:

Przykład

Chcemy zautomatyzować proces przyjmowania kandydatów na praktyki w dużej firmie. Posiadamy setki przykładów z przeszłości, chcemy wydobyć z nich reguły decyzyjne.
Atrybuty:

są kodowane skalą od 1 do 5.

aiwd1.PNG

Na podstawie tabeli decyzyjnej tworzymy drzewo, którego węzłami są poszczególne atrybuty, gałęziami - wartości odpowiadające tym atrybutom, a liście tworzą poszczególne decyzje. Na podstawie przykładowych danych wygenerowano następujące drzewo:

aiwd2.PNG

Drzewo w takiej postaci odzwierciedla, w jaki sposób na podstawie atrybutów były podejmowane decyzje klasyfikujące.

Algorytm

Algorytm działa rekurencyjnie dla każdego węzła drzewa. Musimy podjąć decyzję, czy węzeł będzie:

  1. liściem według kryterium stopu – kończymy to wywołanie rekurencyjne
  2. węzłem rozgałęziającym się według kryterium wyboru atrybutu – dokonujemy wyboru atrybutu, tworzymy rozgałęzienia według wartości, jakie przyjmuje dany atrybut i dla każdego węzła potomnego tworzymy rekurencyjne wywołanie algorytmu, z listą atrybutów zmniejszoną o właśnie wybrany atrybut.

Automatyczne hodowanie drzew

Zastosowanie uczenia maszynowego do generowania drzew decyzyjnych to automatyczne wykrywanie wzorców w danych i tworzenie na ich podstawie schematów podejmowania decyzji.

Algorytm CART

Algorytm CART (ang. Classification and Regression Trees) bazuje na wykorzystaniu struktury drzewa binarnego do predykcji – zarówno klasyfikacji, jak i regresji.

Etapy analizy

  1. ### Kryteria oceny trafności przewidywania: Największą trafność ma model o najmniejszym koszcie klasyfikacji (w większości przypadków przyjmuje się za koszt stosunek przypadków błędnie sklasyfikowanych do wszystkich przypadków).

  2. ### Wybór podziału:

W każdym węźle drzewa wyszukiwany jest podział dający najlepszą trafność predykcji. Najczęściej w metodzie CART stosowane są następujące reguły podziałów: indeks Giniego, miara entropii i reguła podziału na dwie części.

  1. ### Warunek zatrzymania procesu podziału:

Rozszczepianie można przeprowadzać tak długo, aż uzyska się klasyfikację doskonałą. Jednak nie w tym celu stosuje się drzewa decyzyjne. Dlatego też w analizie określa się warunek zatrzymania procesu rozszczepiania. Dla kontroli tego procesu ustala się m.in. minimalną liczność węzłów. Wtedy proces podziału będzie tak długo przeprowadzany aż węzły końcowe będą jednorodne, bądź zawierać będą co najwyżej ustaloną liczbę przypadków.

  1. ### Ustalenie „wielkości” drzewa:

Dobór właściwego rozmiaru drzewa stanowi istotny problem metody CART. Z jednej strony drzewo powinno być jak najprostsze, ale z drugiej strony powinno też prezentować złożoność danych.

Miary zanieczyszczenia

Indeks Giniego

aiwd3.PNG

Entropia

aiwd4.PNG

Przycinanie drzew (ang. pruning)

Nadmiernie dopasowane drzewo charakteryzuje się małym błędem dla danych treningowych, jednak dla danych testowych błąd jest wysoki. Zabieg przycinania ma wyeliminować potencjalny overfitting.

Zadanie

Posiadając dane pasażerów okrętu Titanic wytrenuj drzewo decyzyjne, które jako wynik końcowy będzie klasyfikował czy dana osoba przeżyła, czy też nie.

Zbiór danych

Zbiór danych - atrybuty

  1. PassengerId - liczba porządkowa
  2. Survived    - czy dany pasażer przeżył (0 - nie, 1 - tak)
  3. Pclass      - klasa (1 - pierwsza, 2 - druga, 3 - trzecia)
  4. Name        - pełne imie i nazwisko pasażera
  5. Sex         - płeć pasażera
  6. Age         - wiek pasażera
  7. SibSp       - liczba rodzeństwa / małżonków na pokładzie Titanica
  8. Parch       - liczba rodziców/dzieci na pokładzie Titanica
  9. Ticket      - informacje dotyczące biletu
  10. Fare        - opłata pasażerska
  11. Cabin       - kajuta
  12. Embarked    - port docelowy

Realizacja zadania

Biblioteki

Wczytanie bibliotek potrzebnych do realizacji zadania.

Funkcje

Wstępne formatowanie

Za pomocą 'pandas' ustawiamy formatowanie zmiennych ciągłych z precyzją do dwóch miejsc po przecinku oraz ustawiamy wyświetlanie wszystkich kolumn i wierszy.

Wczytanie zbioru

Prezentacja stanu początkowego zbioru

Typy, braki i ich suma

Usuwanie rekordów / kolumn

Weryfikacja stanu zbioru

Analiza atrybutu - Survived (ocalały/a)

Analiza atrybutu - Sex (płeć)

Analiza atrybutu - Pclass (klasa)

Analiza atrybutu - Age (wiek)

Analiza atrybutu - Embarked (port docelowy)

Analiza atrybutu - SibSp (liczba rodzeństwa / małżonków na pokładzie)

Analiza atrybutu - Parch (liczba dzieci / rodziców na pokładzie)

Analiza atrybutu - Fare (opłata)

Zamiana znaków oraz łańcuchów na wartości liczbowe

Podział zbioru na podzbiór argumentów i wartości

Korelacja

Skalowanie oraz podział na zbiór treningowy i testowy

Zbiór parametrów przekazywany do klasyfikatora

Uczenie klasyfikatora

Najlepszy model klasyfikatora

Wynik na zbiorze testowym

Wizualizacja zbioru wyników

Macierz pomyłek